package tree;

import java.util.*;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/11 9:24
 * @description:
 */
class Tree{
    int val;
    Tree left;
    Tree right;
    Tree(){}
    Tree(int val){this.val = val;}
    Tree(int val,Tree left,Tree right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class PathSum {


}


class solution_pathSum{
    List<List<Integer>> ret = new ArrayList<>();
    Stack<Integer> path = new Stack<>();
    public List<List<Integer>> pathSum(Tree root,int target){
        if(root == null){
            return ret;
        }
        int currsum  = 0;
        findpath(root,target,currsum,path);
        return ret;
    }
    public void findpath(Tree root,int target,int currsum,Stack<Integer> path){

        currsum += root.val;
        path.push(root.val);

        //如果是叶子节点，并且路径上节点值的和等于输入的值
        boolean is_leaf = root.left == null && root.right == null;
        if(currsum == target && is_leaf){
            ret.add(new LinkedList<Integer>(path));
        }
        //不是叶子节点,则遍历它们的子节点
        if(root.left != null){
            findpath(root.left,target,currsum,path);
        }
        if(root.right != null){
            findpath(root.right,target,currsum,path);
        }
        //在返回父节点之前，在路径上删除当前节点
        currsum -= root.val;
        path.pop();
    }
}
